package org.aplombh.java.awcing.basic.basics.sort.mergeSort;

import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
 * <p>
 * 逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
 * <p>
 * 输入格式
 * 第一行包含整数 n，表示数列的长度。
 * <p>
 * 第二行包含 n 个整数，表示整个数列。
 * <p>
 * 输出格式
 * 输出一个整数，表示逆序对的个数。
 * <p>
 * 数据范围
 * 1≤n≤100000，
 * 数列中的元素的取值范围 [1,109]。
 * <p>
 * 输入样例：
 * 6
 * 2 3 4 5 6 1
 * 输出样例：
 * 5
 */
public class CountOfInversePair {

    private static final int N = 100010;

    public static long unencapsulatedInversePair(int[] tmp, int[] ints, int left, int right) {
        if (left >= right) return 0;

        int mid = left + right >> 1;

        // Add the sum of numbers on left partition and right partition inversions
        long res = unencapsulatedInversePair(tmp, ints, left, mid) + unencapsulatedInversePair(tmp, ints, mid + 1, right);

        int k = 0, i = left, j = mid + 1;

        while (i <= mid && j <= right)
            if (ints[i] <= ints[j]) tmp[k++] = ints[i++];
            else {
                tmp[k++] = ints[j++];
                // Add up the sum of the numbers on the left partition that are greater than the numbers on the right partition
                res += mid - i + 1;
            }
        while (i <= mid) tmp[k++] = ints[i++];
        while (j <= right) tmp[k++] = ints[j++];

        for (i = left, j = 0; i <= right; i++, j++) ints[i] = tmp[j];
        return res;
    }

    private static long inversePair(int[] ints) {
        int[] temp = new int[ints.length];
        return unencapsulatedInversePair(temp, ints, 0, ints.length - 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] ints = new int[n];
        IntStream.range(0, n).forEach(i -> {
            ints[i] = scanner.nextInt();
        });
        System.out.println(inversePair(ints));
    }
}
